#pragma once
#include <queue>

using namespace std;

template<typename Graph>
class FindShortestPath
{
public:
	FindShortestPath(Graph& G, int start) : g(G)
	{
		s = start;
		visited = new bool[g.V()];
		from = new int[g.V()];
		level = new int[g.V()];
		for (int i = 0; i < g.V(); ++i)
		{
			visited[i] = false;
			from[i] = -1;
			level[i] = -1;
		}

		PathBFS(s);
	}

	~FindShortestPath()
	{
		delete[] visited;
		delete[] from;
		delete[] level;
	}

	void PathBFS(int v)
	{
		visited[v] = true;
		level[v] = 0;

		queue<int> q;
		q.push(v);
		while (!q.empty())
		{
			int p = q.front();
			q.pop();

			typename Graph::adjIterator it(g, p);
			for (int i = it.begin(); !it.end(); i = it.next())
			{
				if (!visited[i])
				{
					q.push(i);
					visited[i] = true;
					from[i] = p;
					level[i] = level[p] + 1;
				}
			}
		}
	}

	bool HasPath(int w)
	{
		return visited[w];
	}

	void Path(int w, vector<int>& path)
	{
		for (int i = 0; i < g.V(); ++i)
		{
			cout << from[i] << ", ";
		}

		stack<int> stk;
		int p = w;
		while (from[p] != -1)
		{
			stk.push(p);
			p = from[p];
		}
		stk.push(s);

		while (!stk.empty())
		{
			path.push_back(stk.top());
			stk.pop();
		}
	}

	void ShowPath(int w)
	{
		vector<int> path;
		Path(w, path);
		cout << typeid(Graph).name() << " path is :";
		for (auto& e : path)
		{
			cout << e << ", ";
		}
		cout << endl;
	}

	int Level(int w)
	{
		return level[w];
	}

private:
	Graph& g;
	int s;
	bool *visited;
	int *from;
	int *level;
};